package canPartition;

import java.util.Arrays;

public class Solution {
    
    public boolean canPartition(int[] nums) {
        // 01背包问题
        // 动态规划实现
        // 每个数字都只有选和不选两种状态
        // 如果要能够分成等和的两部分，
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean [][]dp = new boolean[n][target+1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true; // 目标值为0，在不选取任何正整数的情况下，和就为0 == 目标值，所以为true
        }
        dp[0][nums[0]]=true;
        // 每个 数字只有选和不选两种情况  如果不选，dp[i][j] == dp[i-1][j]，就是不选的情况
        // 如果选择 dp[i][j] == dp[i-1][j-nums[i]]  即：选了之后，就看有没有可能的选择使得sum== j-nums[i]，也就是说，要在选了nums[i]之后可以构成加成j
        // 就看有没有组合使得和=j-nums[i];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                 if(nums[i]>j){ // 如果第i个数已经大于目标值了，就不能选了
                     dp[i][j] = dp[i-1][j];
                 }else{
                     dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]; //选和不选只要有一个可以就为true；
                 }
            }
        }
        return dp[n-1][target];
    }
    //   01背包问题
    // dp[i][j]  i-->表示第几个物品 j--->表示当前背包的容量
    // 递推公式 dp[i][j] = Max(dp[i-1][j],dp[i-1][j-w(i)]+v(i));  取和不取  dp[i-1][j]表示不取第i个物品，dp[i-1][j-w(i)]+v(i)表示选取第i个物品
    // 注意，选取的物品必须保证背包容量足够，即j>w(i);
    // 因为选了第i个物品，所以在选了第i个物品之后的最优解就是没选第i个物品的时候的最优解加上选了第i个物品。保证每个格子都是当前情况下的最优解
    //   比如 西瓜 3 斤 15
    //       苹果 1 斤 6
    //       香蕉 2 斤 10
    //       榴莲 4 斤 23
    //   背包最大容量 6 斤
    //      背包容量
    // 物品  0  1    2    3    4    5    6
    //   0  0  0    0    0    0    0    0
    // 西瓜3 0  0    0    15   15   15   15
    // 苹果1 0  6    6    15   21   21   21
    // 香蕉2 0  6    10   16   21   25   31
    // 榴莲4 0  6    10   16   23   29   33
//    public static void main(String[] args) {
//        test();
//    }
//    private static void test(){
//        int[] w = new int[]{0,3,1,2,4};// 表示第i个物品的重量
//        int[] v = new int[]{0,15,6,10,23};//表示第i个物品的价值
//        int[][] dp = new int[w.length][7];
//        for (int i = 1; i < dp.length; i++) {
//            for (int j = 1; j < dp[i].length; j++) {
//                // 先判断当前背包容量是否够
//                if(j>=w[i]){
//                    // 选和不选
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
//                }else{
//                    dp[i][j] = dp[i-1][j]; //如果当前背包容量不够，就不选
//                }
//            }
//        }
//        for (int i = 0; i < dp.length; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }
//    }

}
